package com.lxl.merge;

import java.util.Arrays;
import java.util.Collections;

/**
 * @Classname MergeSort
 * @Description 归并排序
 * 稳定
 * O(N*logN)
 * @Date 2021/8/14 9:53
 * @Created by LXLDEMO
 */
public class MergeSort {
    public static void main(String[] args) {
        // 测试数据
        int[] arr = {2,4,3,1,6,5};
//        mergeSort(arr);

    }

    /**
     * 归并排序（重载）
     * 为了创建临时数组 完成数组的复用
     *
     * @param arr 无序数组
     */
    public static void mergeSort(int[] arr){
        System.out.println("初始数据" + Arrays.toString(arr));
        int[] temp = new int[arr.length];
        mergeSort(arr,temp,0,arr.length-1);
    }

    /**
     * 归并排序
     * @param arr
     * @param temp
     * @param start
     * @param end
     */
    public static void mergeSort(int[] arr,int[] temp,int start,int end){
       if (start >= end){
           return;
       }
       int mid = (start + end) / 2;
       // 排序第一个数组
       mergeSort(arr,temp,start,mid);
       // 排序第二个数组
       mergeSort(arr,temp,mid+1,end);
       // 合并两个有序数组
       merge(arr,temp,start,mid,end);
    }

    /**
     * 二路归并 合并两个有序序列
     * 现将两个有序序列合并成一个序列 然后开始排序
     * @param arr   存放两个有序列表的数组
     * @param temp  临时数组
     * @param start 左侧有序列表开始的下标
     * @param mid   左侧结束位置下标  右侧开始位置下标：mid+1
     * @param end   右侧有序列表结束下标
     */
    public static void merge(int[] arr,int[] temp,int start,int mid,int end){
        System.out.println("前一组开始下标 "+start);
        System.out.println("前一组结束下标 "+mid);
        System.out.println("后一组开始下标 "+(mid+1));
        System.out.println("后一组结束下标 "+end);
        int i = start; // i 用来记录 第一个数组的遍历位置
        int j = mid + 1; // 用来记录第二个数组的遍历位置
        int k = start; // 用来表示临时数组的下标
        // i=mid+1:第一个数组先遍历完成
        // j=end+1:第二个数组先遍历完成
        while (i != mid +1 && j != end +1){
            if (arr[i]>arr[j]){
                temp[k++] = arr[j++];
            }else {
                temp[k++] = arr[i++];
            }
        }
        // 第一个数组没有遍历完毕
        while (i != mid + 1){
            temp[k++] = arr[i++];
        }

        // 第二个元素没有遍历完毕
        while (j != end + 1){
            temp[k++] = arr[j++];
        }

        for (int n = start;n<=end;n++){
            arr[n] = temp[n];
        }
        System.out.println("本次合并结果："+Arrays.toString(arr));
    }


}
